/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._86;

/**
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._86
 * @ClassName: Partition
 * @Author: linyaonan
 * @Date: 2020/3/26 16:01
 */
public class Partition {

    public ListNode partition(ListNode head, int x) {
        ListNode leftStart = new ListNode(-1);
        ListNode left = leftStart.next;
        ListNode rightStart = new ListNode(-1);
        ListNode right = rightStart.next;

        while (head != null) {
            int nodeValue = head.val;
            if (nodeValue < x) {
                if (left == null) {
                    leftStart.next = left = new ListNode(nodeValue);
                } else {
                    left = left.next = new ListNode(nodeValue);
                }
            } else {
                if (right == null) {
                    rightStart.next = right = new ListNode(nodeValue);
                } else {
                    right = right.next = new ListNode(nodeValue);
                }
            }
            head = head.next;
        }
        if (left != null) {
            left.next = rightStart.next;
        } else {
            leftStart.next = rightStart.next;
        }

        return leftStart.next;
    }

}
